//
// Created by Semir on 2020/5/10.
//

#include <iostream>
#include <cstring>

using namespace std;

bool vis[2500];
int dirX[4] = {0, -1, 0, 1};
int dirY[4] = {1, 0, -1, 0};

bool dfs(const char* matrix, const char* str, int index, int rows, int cols, int x, int y) {
    if (str[index] == '\0') {
        return true;
    }
    if (matrix[x * cols + y] != str[index]) {
        return false;
    }
    if (str[index + 1] == '\0') {
        return true;
    }
    for (int i = 0; i < 4; i++) {
        int dx = x + dirX[i];
        int dy = y + dirY[i];
        if (dx >= 0 && dx < rows && dy >= 0 && dy < cols && !vis[dx * cols + dy]) {
            vis[dx * cols + dy] = true;
            if (dfs(matrix, str, index + 1, rows, cols, dx, dy)) {
                return true;
            }
            vis[dx * cols + dy] = false;
        }
    }
    return false;
}

bool hasPath(char* matrix, int rows, int cols, char* str) {
    if (matrix == nullptr || str == nullptr || rows <= 0 || cols <= 0) {
        return false;
    }
    memset(vis, 0, sizeof(vis));
    for (int x = 0; x < rows; x++) {
        for (int y = 0; y < cols; y++) {
            vis[x * cols + y] = true;
            if (dfs(matrix, str, 0, rows, cols, x, y)) {
                return true;
            }
            vis[x * cols + y] = false;
        }
    }
    return false;
}

int main() {
//    char matrix[16] = {'a', 'b', 'c', 'e', 's', 'f', 'c', 's', 'a', 'd', 'e', 'e'};
//    char str[6] = {'b', 'c', 'c', 'e', 'd', '\0'};
//    char str[5] = {'a', 'b', 'c', 'b'};
    char* matrix = "ABCESFCSADEE";
    char* str = "SEE";
    bool res = hasPath(matrix, 3, 4, str);
    cout << res << endl;
    return 0;
}
